// // No.1  O(n^3) for for for
// #include <stdio.h>
// int main()
// {
//   int NUM_in;
//   scanf("%d", &NUM_in);
//   int in[100000];//input all integers
//   int Test_SUM = 0, Final_SUM;
//   int i, j, k;//for for loop
//   for (i = 0; i < NUM_in; i++)
//   {
//     scanf("%d", &in[i]);
//   }
  
//   for (i = 0;i<NUM_in; i++)
//   {
//     for (j = i;j<NUM_in;j++)
//     {
//       Test_SUM = 0;
//       for (k = i; k <= j;k++)
//       {
//         Test_SUM += in[k];
//         if (Test_SUM>Final_SUM)
//         {
//           Final_SUM = Test_SUM;
//         }
        
//       }
//     }
//   }
//   printf("%d", Final_SUM);
//   return 0;
// }

// No.2  O(n^2) for for
// #include <stdio.h>
// int main()
// {
//   int NUM_in;
//   scanf("%d", &NUM_in);
//   int in[100000];//input all integers
//   int Test_SUM, Final_SUM=0;
//   // int Max_in = -999999;
//   int i, j, k;//for for loop
//   for (i = 0; i < NUM_in; i++)
//   {
//     scanf("%d", &in[i]);
//   }
  
//   for (i = 0;i<NUM_in; i++)
//   {
//     Test_SUM = in[i];
//     for (j = i+1;j<NUM_in;j++)
//     {
//       Test_SUM += in[j];
//       if (Test_SUM>Final_SUM)
//       {
//         Final_SUM = Test_SUM;
//       }
      
//     }
//   }
//   printf("%d", Final_SUM);
//   return 0;
// }

// // No.3 divde O(NlogN)
// #include <stdio.h>
// int Max3(int A,int B,int C)
// {
//   return A > B ? A > C ? A : C : B > C ? B : C;
// }
// int DivideAndConquer( int List[], int left, int right )
// { /* 分治法求List[left]到List[right]的最大子列和 */
//     int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
//     int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/

//     int LeftBorderSum, RightBorderSum;
//     int center, i;

//     if( left == right )  { /* 递归的终止条件，子列只有1个数字 */
//         if( List[left] > 0 )  return List[left];
//         else return 0;
//     }

//     /* 下面是"分"的过程 */
//     center = ( left + right ) / 2; /* 找到中分点 */
//     /* 递归求得两边子列的最大和 */
//     MaxLeftSum = DivideAndConquer( List, left, center );
//     MaxRightSum = DivideAndConquer( List, center+1, right );

//     /* 下面求跨分界线的最大子列和 */
//     MaxLeftBorderSum = 0; LeftBorderSum = 0;
//     for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
//         LeftBorderSum += List[i];
//         if( LeftBorderSum > MaxLeftBorderSum )
//             MaxLeftBorderSum = LeftBorderSum;
//     } /* 左边扫描结束 */

//     MaxRightBorderSum = 0; RightBorderSum = 0;
//     for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
//         RightBorderSum += List[i];
//         if( RightBorderSum > MaxRightBorderSum )
//             MaxRightBorderSum = RightBorderSum;
//     } /* 右边扫描结束 */

//     /* 下面返回"治"的结果 */
//     return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
// }
// int MaxSubseqSum3( int List[], int N )
// { /* 保持与前2种算法相同的函数接口 */
//     return DivideAndConquer( List, 0, N-1 );
// }
// int main()
// {
//   int NUM_in;
//   scanf("%d", &NUM_in);
//   int in[100000];//input all integers
//   int Test_SUM, Final_SUM=0;
//   // int Max_in = -999999;
//   int i, j, k;//for for loop
//   for (i = 0; i < NUM_in; i++)
//   {
//     scanf("%d", &in[i]);
//   }

//   Final_SUM=DivideAndConquer(in, 0, NUM_in);
//   printf("%d", Final_SUM);
//   return 0;
// }


// No.4 online searching
// #include <stdio.h>
// int main()
// {
//   int NUM_in;//number of input integer
//   scanf("%d", &NUM_in);
//   int in[100000];//input all integers
//   int i, temp, Test_SUM = 0, Final_SUM,Max_in=-99999;
//   for (i = 0; i < NUM_in; i++)
//   {
//     scanf("%d", &in[i]);
//     if(in[i]>Max_in)
//     {
//       Max_in = in[i];
//     }
//   }
//   Final_SUM = Max_in;
//   for (i = 0;i<NUM_in;i++)
//   {

//     Test_SUM += in[i];
//     if (Test_SUM > Final_SUM)
//     {
//       Final_SUM = Test_SUM;
//     }
//     else if (Test_SUM < Max_in && Max_in <0)
//     {//if the max integer is negative we need initial test_sum to max integer since we still need sum the negative max_in
//       Test_SUM = Max_in;
//     }
//     else if (Test_SUM < 0 && Max_in >0)
//     {//if the max integer is positive the test sum can just be zero since we already have final_sum=max integer
//       Test_SUM = 0;
//     }
    
//   }
//     printf("%d", Final_SUM);
//   //online ranking sum

//   return 0;
// }
